package LinkedList;

/**
 *  题目 ：分割链表
 *  题目详解 ：
 *  给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 *
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 *
 */
public class P86 {
    /**
     * 核心思想 ：
     * 维护两条Small和Big链表；小于x的节点加入到Small链表中去，大于或者等于x的节点则是要加入到Big链表中；
     * 特殊情况 ：
     * （1）small链表的尾节点指向big链表的头节点
     * （2）big链表的尾节点指向null值；
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        // 构建两条链表small 和 big链表（先是设立其哨兵节点，再是定义节点[为了进行节点的移动和改变]指向其哨兵节点）
        ListNode small = new ListNode(0);  // small链表的哨兵节点
        ListNode smallHead = small;            // small链表的尾节点（需要将其指向big链表的头节点）
        ListNode big = new ListNode(0);    // big链表的哨兵节点
        ListNode bigHead = big;                // big链表的尾节点（由于尾节点的next指针指向的不一定为null，需要将其置为null值）
        while(head != null){
            if(head.val < x){
                smallHead.next = head;
                smallHead = smallHead.next;
            }
            else {
                bigHead.next = head;
                bigHead = bigHead.next;
            }
            head = head.next;
        }
        // 使得small链表的尾节点指向big链表的头节点
        smallHead.next = big.next;
        // 由于Big链表中的尾节点是从原链表中直接引入的，所以可能尾节点.next指向的是另一个节点，
        // ===> 我们需要将Big链表的 尾节点.next置为null
        bigHead.next = null;
        return small.next;
    }
}
